<html>
<head>
 <title>City Tour</title>
</head>

<body>

<center>
<h1>POI VIII Stage 3 Problem 3</h1>
<h1>City Tour</h1>
</center>

<p>The Tourist Agency of Byteland (abbr. TAB) is about to start its activity with
offering a tour along the streets of Bytenburg in a cabriolet-bus. The centre of
the company - the place where every tour will start and finish - needs to be built.
The route of the tour must include every street of the city, otherwise tourists
may suspect they had missed something really interesting. The streets don't have
to be straight and they may go through tunnels or viaducts. There are no one way
streets in the city. Each street connects two crossroads. There are streets going
out of each crossroads in four directions. It is possible that there are two crossroads
connected by more than one street. It is not allowed to turn round (and go in
the opposite direction) on
the streets, but you can do it on crossroads. Moreover, it is possible to drive
from any crossroads to any other one by the system of the streets. Exactly in the middle of each
street there is some tourist object, which is especially interesting to see (e.g. some breathtaking
view, a sculpture or a monument). We describe the degree of attraction of such
object by a non-negative integer. The centre of&nbsp; the TAB should be built
in the middle of a street, beside one of these objects. While
planning a tour, we need to consider the interest of tourists (how much the tour
was interesting for them) which varies during the sightseeing. Traveling by bus
through one byte-mile causes the lost of one unit in the interest of tourists.
Visiting an object <u>for the first
time</u> causes the raise of interest of tourists by the number describing the
degree of attraction of this object. At the beginning of a
tour the interest is equal to the degree of attraction of the object beside the
center of the TAB. We say that the route of the trip is attractive if the interest
never falls below zero
during the trip.

<h2>Task</h2>
<p>Write a program which:</p>
<ul>
  <li>reads the description of the city from the text file ZWI.IN,</li>
  <li>finds the route of a tour fulfilling the given conditions (i.e. attractive
    one), or answers that
    there is no such a route</li>
  <li>writes the result to the text file ZWI.OUT.</li>
</ul>

<h2>Input</h2>
<p>In the first line of the text file ZWI.IN there is one integer <i>n</i> equal
to the number of crossroads in the city, <i>1&lt;n&lt;=10&nbsp;000. </i>The crossroads
are numbered from 1 to <i>n</i>, and streets are numbered from 1 to 2<i>n</i>.
The following 2<i>n</i> lines describe the streets of the city. In the (<i>i</i>+1)-st
line the <i>i</i>-th street is described. The description is composed of
four integers <i>a, b, l, s</i>, separated by single spaces. The integers <i>a</i>
and <i>b</i> denote the numbers of crossroads connected by this street,&nbsp; <i>1&lt;=a,b&lt;=n</i>,
<i>a&lt;&gt;b</i>. The integer <i>l</i> is even and denotes the length of the
street in byte-miles, <i>2&lt;=l&lt;=1&nbsp;000</i>. The degree of attraction of
the abject situated on this street is described by the number <i>s</i>, <i>0&lt;=s&lt;=1&nbsp;000</i>.</p>

<h2>Output</h2>
<p>The first line of the text file ZWI.OUT should contain one word &quot;TAK&quot;
(<i>&quot;yes&quot; in Polish</i>), if there exists an attractive route in the city, otherwise
there should be written the word &quot;NIE&quot; (<i>&quot;no&quot; in Polish</i>). If
the answer is positive, the following lines should describe one of the possible
attractive routes. The second line should contain exactly one integer <i>k</i> equal to the
number of crossroads on the route. (Remember that the street with the centre of the
TAB must connect the first crossroads on the route with the last one.) We denote
by <i>s<sub>i</sub></i> (for <i>i=1,2,...,k</i>) the number of the street we use
to get to the crossroads that is <i>i</i>-th on this route. The third line of the
output file should contain two integers: <i>s<sub>1</sub></i> equal
to the number of the street with the centre of the TAB and <i>d</i> equal to the number of the
first crossroads on the route. Each of the following <i>k</i>-1 lines should
contain one integer&nbsp; ---&nbsp; <i>s<sub>2</sub></i>, <i>s<sub>3</sub></i>,
..., <i>s<sub>k</sub></i> respectively.</p>

<h2>Sample Input</h2>
<pre>4
1 2 4 6
2 4 2 4
3 2 4 2
4 3 10 8
2 1 8 7
4 3 2 1
1 4 2 6
3 1 4 5
</pre>

<h2>Sample Output</h2>
<pre>TAK
8
5 2
2
6
3
1
8
4
7
</pre>

</body>

</html>
